package tree;

/**
 * @author : Rookie
 * @description : 二叉搜索树的最近公共祖先
 * @date : 2023/10/29
 */
public class BinarySearchTreeAncestor {

    public static void main(String[] args) {
        int[] tree = new int[] {6,2,8,0,4,7,9,-1,-1,3,5,-1,-1,-1,-1};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
        // 求节点p和q的最近公共祖先
        TreeNode ancestor = getAncestor(root, 3, 4);
        System.out.println(ancestor);
    }

    private static TreeNode getAncestor(TreeNode node,int p,int q) {
        if (node == null || node.element == p || node.element == q) {
            return node;
        }
        // 第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。
        if (node.element > p && node.element < q) {
            // 左
            TreeNode left = getAncestor(node.left, p, q);
            if (left != null) {
                return left;
            }
        }
        // 因为不知道是p大还是q大 所以需要再次判断
        if (node.element > q && node.element <p) {
            // 右
            TreeNode right = getAncestor(node.right, p, q);
            if (right != null) {
                return right;
            }
        }
        return node;
    }
}
